Cheapest Flights Within K Stops
2020/6/14
問題概要
https://gyazo.com/3dfcbc859b6a01487c37b076b63901df
N数の街とそれらをつなぐフライト航路が与えられる
航路には、それぞれ出発地・到着地・料金がある
ある出発地から到着地までで、k数のステップで最小となる金額を求めよ、という問題
解法
queueを使って走査していき、queueが空もしくはkの上限に達したら終了 終了した時点で最小の金額になってる値を返せばok
時間計算量
$ O(N \times K)
最悪計算量としては、最大深さK(正確にはK-1)においてそれぞれノード数Nを探索する必要があるため.
空間計算量
$ O(N^2 + N \times K)
map部分でフライト情報を格納していて、これに$ O(N^2)かかる
queue部分でKステップまで格納し続けるので最悪計算量としては$ O(N \times K)になる
解くのにかかった時間
合計32分
方針に2分
実装等に30分
うちデバッグに(恐らく)15分くらい？
参照周りを雑に書いたらバグったので、確実に参照使ってokそうなflight周りに絞り、
かつ値段周りで枝切りしたらTLEも発生せず無事通った code:solution.cpp
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
map<int, vector<vector<int>>> m;
for (vector<int>& f : flights) {
if (m.count(f0)) m[f0].push_back({f1, f2}); }
int price = INT_MAX;
queue<vector<int>> q;
if (!m.count(src)) return -1;
for (vector<int> v : msrc) q.push({v0, v1, 0}); while (!q.empty() && q.front()2 <= K) { vector<int> p = q.front();
q.pop();
// pruning redundant processing
if (price < p1) continue; // arrived at dst
if (p0 == dst) price = min(price, p1); // cannot visit anymore
if (!m.count(p0)) continue; for (vector<int> v : m[p0]) q.push({v0, p1 + v1, p2+1}); }
if (price == INT_MAX) price = -1;
return price;
}
};